package n_05;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author ChengMiao
 * @date 2021/6/29 11:01
 * @Desc No.5 最长回文字符串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 */
public class Demo {

    public static void main(String[] args) {

//        String s = "babad";
        String s = "flsuqzhtcahnyickkgtfnlyzwjuiwqiexthpzvcweqzeqpmqwkydhsfipcdrsjkefehhesubkirhalgnevjugfohwnlhbjfewiunlgmomxkafuuokesvfmcnvseixkkzekuinmcbmttzgsqeqbrtlwyqgiquyylaswlgfflrezaxtjobltcnpjsaslyviviosxorjsfncqirsjpkgajkfpoxxmvsyynbbovieoothpjgncfwcvpkvjcmrcuoronrfjcppbisqbzkgpnycqljpjlgeciaqrnqyxzedzkqpqsszovkgtcgxqgkflpmrikksaupukdvkzbltvefitdegnlmzeirotrfeaueqpzppnsjpspgomyezrlxsqlfcjrkglyvzvqakhtvfmeootbtbwfhqucbnuwznigoyatvkocqmbtqghybwrhmyvvuchjpvjckiryvjfxabezchynfxnpqaeampvaapgmvoylyutymdhvhqfmrlmzkhuhupizqiujpwzarnszrexpvgdmtoxvjygjpmiadzdcxtggwamkbwrkeplesupagievwsaaletcuxtpsxmbmeztcylsjxvhzrqizdmgjfyftpzpgxateopwvynljzffszkzzqgofdlwyknqfruhdkvmvrrjpijcjomnrjjubfccaypkpfokohvkqndptciqqiscvmpozlyyrwobeuazsawtimnawquogrohcrnmexiwvjxgwhmtpykqlcfacuadyhaotmmxevqwarppknoxthsmrrknu";

//        String s = "ccc";
        System.out.println(System.currentTimeMillis());
        System.out.println(longestPalindrome(s));
        System.out.println(System.currentTimeMillis());

    }

    public static String longestPalindrome(String s) {

        char[] arr = s.toCharArray();

        if(arr.length<2){
            return s;
        }

        if(Objects.equals(s,new StringBuffer(s).reverse().toString())){
            return s;
        }

        String str = "";
        String returnStr = "";

        int index = 0;

        for (int i = 0; i < arr.length; i++) {
            str += arr[i];

            for (int j = i+1; j <arr.length ; j++) {
//                String newStr = str.substring(1); // 去除一个
//                if(!Objects.equals(newStr,new StringBuffer(newStr).reverse().toString())) { // 不满足回文串 不再往下迭代
//                    str = "";
//                    break;
//                }

                str += arr[j];

                if(Objects.equals(str,new StringBuffer(str).reverse().toString())){ // 回文串
                    if(index< str.length()){
                        index = str.length();
                        returnStr = str;
//                        str = "";
                    }
                }

                if(j==arr.length-1){
                    str = "";
                }
            }
        }

        return returnStr.isEmpty()?String.valueOf(arr[0]):returnStr;

    }
}
